package com.dataStructures.sort;

import java.util.Arrays;

/**
 * 选择排序（时间复杂度 O(n^2)）
 */
public class SelectSort {
	public static void main(String[] args) {
		int[] arr = {3, 9, -1, 10, 20};
		System.out.println("排序前：" + Arrays.toString(arr));
		selectSort(arr);
		System.out.println("排序后：" + Arrays.toString(arr));

		// 批量测试
		int[] arrBatch = new int[80000];
		for (int i = 0; i < 80000; i++) {
			arrBatch[i] = (int) (Math.random() * 8000000);
		}
		long begin = System.currentTimeMillis();
		selectSort(arrBatch);
		System.out.println("coast time:" + (System.currentTimeMillis() - begin));
	}

	public static void selectSort(int[] arr) {
		// 最小值选取的次数
		for (int i = 0; i < arr.length - 1; i++) {
			// 假定最小值是每次比较范围的第一个
			int min = arr[i];
			int minIndex = i;
			// 每轮选出最小值需要比较的次数
			for (int j = i + 1; j < arr.length; j++) {
				if (min > arr[j]) {
					min = arr[j];
					minIndex = j;
				}
			}
			// 如果最小值不是最开始假定的位置，则将最小值放在每次比较范围的首个位置(只交换值)（注意：此处是 i，即每次比较范围的首个位置）
			if (minIndex != i) {
				arr[minIndex] = arr[i];
				arr[i] = min;
			}
		}
	}
}
